home *** CD-ROM | disk | FTP | other *** search
/ Chip 2007 January, February, March & April / Chip-Cover-CD-2007-02.iso / Pakiet multimedia / Animacje, filmy i prezentacje / Modelowanie 3D / K-3D 0.6.5.0 / k3d-all-in-one-setup-0.6.5.0.exe / aqsis-setup-1.1.0-2006-12-09.exe / include / aqsis / bitvector.h < prev    next >
Encoding:
C/C++ Source or Header  |  2006-06-14  |  7.9 KB  |  272 lines
  1. // Aqsis
  2. // Copyright ⌐ 1997 - 2001, Paul C. Gregory
  3. //
  4. // Contact: pgregory@aqsis.org
  5. //
  6. // This library is free software; you can redistribute it and/or
  7. // modify it under the terms of the GNU General Public
  8. // License as published by the Free Software Foundation; either
  9. // version 2 of the License, or (at your option) any later version.
  10. //
  11. // This library is distributed in the hope that it will be useful,
  12. // but WITHOUT ANY WARRANTY; without even the implied warranty of
  13. // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14. // General Public License for more details.
  15. //
  16. // You should have received a copy of the GNU General Public
  17. // License along with this library; if not, write to the Free Software
  18. // Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
  19.  
  20.  
  21. /** \file
  22.         \brief Declares the CqBitVector class for handling efficient bit vectors of any length.
  23.         \author Paul C. Gregory (pgregory@aqsis.org)
  24. */
  25.  
  26. //? Is .h included already?
  27. #ifndef BITVECTOR_H_INCLUDED
  28. #define BITVECTOR_H_INCLUDED 1
  29.  
  30. #include    <iostream>
  31.  
  32. #include    "aqsis.h"
  33.  
  34. START_NAMESPACE( Aqsis )
  35.  
  36. typedef unsigned char    bit;
  37.  
  38. /// Define the number of bits in a char
  39. #ifndef CHAR_BIT
  40. #define    CHAR_BIT    8
  41. #endif
  42.  
  43. //----------------------------------------------------------------------
  44. /**
  45.     \brief Varying length bitvectors.
  46.     Provide the functionality of any length bitvectors and logic operations between them.
  47.  
  48. */
  49.  
  50. class CqBitVector
  51. {
  52.     public:
  53.         /** Default constructor.
  54.          * \param size the initial size of the bit vector.
  55.          */
  56.         CqBitVector( TqInt size = 0 ) : m_aBits( 0 ), m_cLength( 0 ), m_cNumInts( 0 )
  57.         {
  58.             if ( size > 0 )
  59.                 SetSize( size );
  60.         }
  61.         /** Copy constructor.
  62.          * \param from the bitvector to copy.
  63.          */
  64.         CqBitVector( const CqBitVector& from ) : m_aBits( 0 ), m_cLength( 0 ), m_cNumInts( 0 )
  65.         {
  66.             *this = from;
  67.         }
  68.         ~CqBitVector()
  69.         {
  70.             delete[] ( m_aBits );
  71.         }
  72.  
  73.         /** Get the size of the bit vector.
  74.          * \return integer size.
  75.          */
  76.         TqInt    Size() const
  77.         {
  78.             return ( m_cLength );
  79.         }
  80.         /** Set the size of the bitvector.
  81.          * \warning If the bit vector grows, the contents of any additional bits is undefined.
  82.          * \param size the new size of the bit vector.
  83.          */
  84.         void    SetSize( TqInt size )
  85.         {
  86.             TqInt cNumInts = NumberOfInts( size );
  87.             if ( m_cNumInts != cNumInts )
  88.             {
  89.                 delete[] ( m_aBits );
  90.                 m_cNumInts = NumberOfInts( size );
  91.                 m_aBits = new bit[ m_cNumInts ];
  92.             }
  93.             m_cLength = size;
  94.         }
  95.  
  96.         /** Force the array om canonical form, i.e. all unused bits in the char array are zeroed.
  97.          */
  98.         void    Canonize()
  99.         {
  100.             ( m_aBits ) [ m_cNumInts - 1 ] &= ( bit ) ~0 >> ( CHAR_BIT - ( ( m_cLength % CHAR_BIT )
  101.                                               ? ( m_cLength % CHAR_BIT )
  102.                                               : CHAR_BIT ) );
  103.         }
  104.         /** Set the indexed bit to the boolean value specified.
  105.          * \param elem the index of the bit to modify.
  106.          * \param value the new value of the bit, 0-false, 1-true.
  107.          */
  108.         void    SetValue( TqInt elem, TqBool value )
  109.         {
  110.             assert( elem < m_cLength );
  111.             if ( value )
  112.                 m_aBits[ elem / CHAR_BIT ] |= ( 1 << ( elem % CHAR_BIT ) );
  113.             else
  114.                 m_aBits[ elem / CHAR_BIT ] &= ~( 1 << ( elem % CHAR_BIT ) );
  115.         }
  116.         /** Get the indexed bit as a boolean.
  117.          * \param elem the index of the bit to retrieve.
  118.          */
  119.         TqBool Value( TqInt elem )
  120.         {
  121.             assert( elem < m_cLength );
  122.             return ( ( m_aBits[ elem / CHAR_BIT ] & ( 1 << ( elem % CHAR_BIT ) ) ) ? TqTrue : TqFalse );
  123.         }
  124.         /** Toggle the state of the indexed bit.
  125.          * \param elem the index of the bit to modify.
  126.          */
  127.         void    Toggle( TqInt elem )
  128.         {
  129.             assert( elem < m_cLength );
  130.             m_aBits[ elem / CHAR_BIT ] ^= ( 1 << ( elem % CHAR_BIT ) );
  131.         }
  132.         /** Set all bits to the specified value.
  133.          * \param value the new value of the bit, 0-false, 1-true.
  134.          */
  135.         void    SetAll( TqBool value )
  136.         {
  137.             bit setval = ( value ) ? ~0 : 0;
  138.             register TqInt i;
  139.  
  140.             for ( i = 0; i < m_cNumInts; i++ )
  141.                 m_aBits[ i ] = setval;
  142.             Canonize();
  143.         }
  144.         /** Invert the state of all bits in the vector.
  145.          */
  146.         void    Complement()
  147.         {
  148.             register TqInt i;
  149.  
  150.             for ( i = 0; i < m_cNumInts; i++ )
  151.                 m_aBits[ i ] = ~m_aBits[ i ];
  152.             Canonize();
  153.         }
  154.         /// Count the number of 1 bits in the vector.
  155.         TqInt    Count();
  156.         /// Boolean intersection.
  157.         CqBitVector&    Intersect( CqBitVector& from );
  158.         /// Boolean union.
  159.         CqBitVector&    Union( CqBitVector& from );
  160.         /// Boolean difference.
  161.         CqBitVector&    Difference( CqBitVector& from );
  162.         /** Assignment operator.
  163.          * \param from the bitvector to copy.
  164.          * \return a reference to this bit vector.
  165.          */
  166.         CqBitVector& operator=( const CqBitVector& from )
  167.         {
  168.             // Copy the array of bits
  169.             SetSize( from.m_cLength );
  170.             for ( TqInt i = 0; i < m_cNumInts; i++ )
  171.                 m_aBits[ i ] = from.m_aBits[ i ];
  172.  
  173.             return ( *this );
  174.         }
  175.         /** Perform a bitwise AND on this with the specified bitvector.
  176.          * \param from the bitvector to perform the AND with.
  177.          * \return the result of the AND operation as a new bitvector.
  178.          */
  179.         CqBitVector operator&( CqBitVector& from )
  180.         {
  181.             CqBitVector res( *this );
  182.             res.Intersect( from );
  183.             return ( res );
  184.         }
  185.         /** Perform a bitwise OR on this with the specified bitvector.
  186.          * \param from the bitvector to perform the OR with.
  187.          * \return the result of the OR operation as a new bitvector.
  188.          */
  189.         CqBitVector operator|( CqBitVector& from )
  190.         {
  191.             CqBitVector res( *this );
  192.             res.Union( from );
  193.             return ( res );
  194.         }
  195.         /** Perform a bitwise exclusive OR on this with the specified bitvector.
  196.          * \param from the bitvector to perform the exclusive OR with.
  197.          * \return the result of the exclusive OR operation as a new bitvector.
  198.          */
  199.         CqBitVector operator^( CqBitVector& from )
  200.         {
  201.             CqBitVector res( *this );
  202.             res.Difference( from );
  203.             return ( res );
  204.         }
  205.  
  206.         /** Perform a bitwise AND on this with the specified bitvector, storing the result in this.
  207.          * \param from the bitvector to perform the AND with.
  208.          * \return a reference to this bitvector.
  209.          */
  210.         CqBitVector& operator&=( CqBitVector& from )
  211.         {
  212.             Intersect( from );
  213.             return ( *this );
  214.         }
  215.         /** Perform a bitwise OR on this with the specified bitvector, storing the result in this.
  216.          * \param from the bitvector to perform the OR with.
  217.          * \return a reference to this bitvector.
  218.          */
  219.         CqBitVector& operator|=( CqBitVector& from )
  220.         {
  221.             Union( from );
  222.             return ( *this );
  223.         }
  224.         /** Perform a bitwise exclusive OR on this with the specified bitvector, storing the result in this.
  225.          * \param from the bitvector to perform the exclusive OR with.
  226.          * \return a reference to this bitvector.
  227.          */
  228.         CqBitVector& operator^=( CqBitVector& from )
  229.         {
  230.             Difference( from );
  231.             return ( *this );
  232.         }
  233.  
  234.         /** Get the number of bytes required to represent the whole bitvector.
  235.          * \param size the required size of the bitvector.
  236.          * \return an integer count of bytes needed.
  237.          */
  238.         TqInt ArraySize()
  239.         {
  240.             return( NumberOfInts(m_cLength) );
  241.         }
  242.  
  243.         /** Get a pointer to the ints representing the bitvector.
  244.          * \return a pointer to the char array.
  245.          */
  246.         bit* IntArray()
  247.         {
  248.             return ( m_aBits );
  249.         }
  250.         /** Get the number of bytes required to represent the specified number of bits.
  251.          * \param size the required size of the bitvector.
  252.          * \return an integer count of bytes needed.
  253.          */
  254.         static    TqInt    NumberOfInts( TqInt size )
  255.         {
  256.             return ( ( size + ( CHAR_BIT ) - 1 ) / ( CHAR_BIT ) );
  257.         }
  258.         friend std::ostream &operator<<( std::ostream &Stream, CqBitVector &Vector );
  259.     private:
  260.         bit*    m_aBits;            ///< the array of bytes to store the bit vector.
  261.         TqInt    m_cLength;            ///< the size of the bitvector in bits.
  262.         TqInt    m_cNumInts;            ///< the size of the array in bytes.
  263. }
  264. ;
  265.  
  266.  
  267. //-----------------------------------------------------------------------
  268.  
  269. END_NAMESPACE( Aqsis )
  270.  
  271. #endif    // !BITVECTOR_H_INCLUDED
  272.